package com.c2b.algorithm.leetcode.base;

import java.util.PriorityQueue;
import java.util.Queue;

/**
 * <a href='https://leetcode.cn/problems/smallest-number-in-infinite-set/submissions/'>无限集中的最小数字(Smallest Number in Infinite Set)</a>
 * <p>现有一个包含所有正整数的集合 [1, 2, 3, 4, 5, ...] 。</p>
 * <p>
 * 实现 SmallestInfiniteSet 类：
 *     <ul>
 *         <li>SmallestInfiniteSet() 初始化 SmallestInfiniteSet 对象以包含 所有 正整数。</li>
 *         <li>int popSmallest() 移除 并返回该无限集中的最小整数。</li>
 *         <li>void addBack(int num) 如果正整数 num 不 存在于无限集中，则将一个 num 添加 到该无限集中。</li>
 *     </ul>
 * </p>
 * <p>
 * <b>示例：</b>
 * <pre>
 * 输入
 *      ["SmallestInfiniteSet", "addBack", "popSmallest", "popSmallest", "popSmallest", "addBack", "popSmallest", "popSmallest", "popSmallest"]
 *      [[], [2], [], [], [], [1], [], [], []]
 * 输出
 *      [null, null, 1, 2, 3, null, 1, 4, 5]
 *
 * 解释
 *      SmallestInfiniteSet smallestInfiniteSet = new SmallestInfiniteSet();
 *      smallestInfiniteSet.addBack(2);    // 2 已经在集合中，所以不做任何变更。
 *      smallestInfiniteSet.popSmallest(); // 返回 1 ，因为 1 是最小的整数，并将其从集合中移除。
 *      smallestInfiniteSet.popSmallest(); // 返回 2 ，并将其从集合中移除。
 *      smallestInfiniteSet.popSmallest(); // 返回 3 ，并将其从集合中移除。
 *      smallestInfiniteSet.addBack(1);    // 将 1 添加到该集合中。
 *      smallestInfiniteSet.popSmallest(); // 返回 1 ，因为 1 在上一步中被添加到集合中，
 *                                         // 且 1 是最小的整数，并将其从集合中移除。
 *      smallestInfiniteSet.popSmallest(); // 返回 4 ，并将其从集合中移除。
 *      smallestInfiniteSet.popSmallest(); // 返回 5 ，并将其从集合中移除。
 * </pre>
 * </p>
 *
 * <p>
 * <b>提示：</b>
 * <ul>
 *     <li>1 <= num <= 1000</li>
 *     <li>最多调用 popSmallest 和 addBack 方法 共计 1000 次</li>
 * </ul>
 * </p>
 *
 * @author c2b
 * @since 2023/11/14 14:37
 */
public class LC2336SmallestNumberInInfiniteSet_M {

    static class SmallestInfiniteSet {
        /**
         * 下一个要移除的数字
         */
        private int nextRemoveNum = 1;
        /**
         * 小根堆，用于保留 addBack 方法中添加的元素
         */
        private final Queue<Integer> heap;

        public SmallestInfiniteSet() {
            heap = new PriorityQueue<>();
        }

        public int popSmallest() {
            if (!heap.isEmpty() && heap.peek() < nextRemoveNum) {
                return heap.poll();
            }
            return nextRemoveNum++;
        }

        public void addBack(int num) {
            if (!heap.contains(num) && num < nextRemoveNum) {
                heap.offer(num);
            }
        }
    }

    public static void main(String[] args) {
        SmallestInfiniteSet smallestInfiniteSet = new SmallestInfiniteSet();
        smallestInfiniteSet.addBack(2);
        System.out.println(smallestInfiniteSet.popSmallest());
        System.out.println(smallestInfiniteSet.popSmallest());
        System.out.println(smallestInfiniteSet.popSmallest());
        smallestInfiniteSet.addBack(1);
        System.out.println(smallestInfiniteSet.popSmallest());
        System.out.println(smallestInfiniteSet.popSmallest());
        System.out.println(smallestInfiniteSet.popSmallest());
    }
}
